home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / prog / plane / sweep1.c < prev   
Encoding:
C/C++ Source or Header  |  1994-08-05  |  11.8 KB  |  428 lines
  1. #include <LEDA/sweep_segments.h>
  2. #include <LEDA/plane.h>
  3. #include <LEDA/sortseq.h>
  4. #include <LEDA/prio.h>
  5.  
  6. #include <LEDA/impl/bin_heap.h>
  7. #include <LEDA/impl/p_heap.h>
  8.  
  9. #include <LEDA/impl/skiplist.h>
  10. #include <LEDA/impl/bin_tree.h>
  11. #include <LEDA/impl/avl_tree.h>
  12. #include <LEDA/impl/rb_tree.h>
  13. #include <LEDA/impl/rs_tree.h>
  14.  
  15. #include <math.h>
  16.  
  17. #define EPS 1e-10
  18.  
  19. double x_sweep;
  20. double y_sweep;
  21.  
  22. int compare(segment& s1, segment& s2)  
  23. {
  24.   // compare vertical distance at x = x_sweep
  25.   // compare slopes in case of intersection
  26.  
  27.   double y1 = s1.y_proj(x_sweep);
  28.   double dy = y1 - s2.y_proj(x_sweep);
  29.  
  30.   if (dy >  EPS ) return  1;
  31.   if (dy < -EPS ) return -1;
  32.  
  33.   if (y1 <= y_sweep)
  34.         return compare(s1.slope(),s2.slope());  // below current y-coordinate
  35.   else
  36.         return compare(s2.slope(),s1.slope());  // above current y-coordinate
  37.  }
  38.  
  39.  
  40. int cmp_seg(const segment& s1, const segment& s2) // compare by left endpoint
  41. { return compare(s1.start(),s2.start()); }
  42.  
  43.  
  44. void SWEEP(priority_queue<seq_item,point>& X_structure,
  45.            sortseq<segment,pq_item>&       Y_structure,
  46.            const list<segment>&            L, 
  47.            list<point>&                    result)
  48. {
  49.   // The Sweep
  50.  
  51.   list<segment>  segment_queue;
  52.  
  53.   pq_item  pqit;
  54.   seq_item sit,sit_pred,sit_succ;
  55.   segment  seg,seg_pred,seg_succ;
  56.   point    p,q;
  57.  
  58.   result.clear();
  59.  
  60.   Y_structure.insert(segment(-MAXINT, MAXINT,MAXINT, MAXINT),nil);
  61.   Y_structure.insert(segment(-MAXINT,-MAXINT,MAXINT,-MAXINT),nil);
  62.  
  63.  
  64.   // initialization of the X-structure and segment queue
  65.  
  66.   forall(seg,L) 
  67.   { if (seg.xcoord1() > seg.xcoord2()) seg = segment(seg.end(),seg.start());
  68.     segment_queue.append(seg);
  69.     X_structure.insert(nil,seg.start());
  70.    }
  71.  
  72.   segment_queue.sort(cmp_seg);   // sort segments by first x-coord
  73.  
  74.  
  75.   x_sweep = -MAXINT;
  76.   y_sweep = -MAXINT;
  77.  
  78.   while( ! X_structure.empty() )
  79.   { 
  80.  
  81.     pqit = X_structure.find_min();
  82.     sit  = X_structure.key(pqit);
  83.     p    = X_structure.inf(pqit);
  84.  
  85.     X_structure.del_item(pqit);
  86.  
  87.     if (sit == nil)   // left end of segment (enter event)
  88.     { 
  89.       seg = segment_queue.pop();   // next segment to enter the Y-structure
  90.  
  91.       x_sweep = p.xcoord();
  92.       y_sweep = p.ycoord();
  93.  
  94.       if (p.xcoord() == seg.xcoord2())
  95.            error_handler(1,"plane sweep: sorry, vertical segment");
  96.  
  97.       if (Y_structure.lookup(seg) != nil)
  98.            error_handler(1,"plane sweep: sorry, overlapping segments");
  99.  
  100.  
  101.       sit = Y_structure.insert(seg,nil);
  102.  
  103.       X_structure.insert(sit,seg.end());
  104.  
  105.       sit_pred = Y_structure.pred(sit);
  106.       sit_succ = Y_structure.succ(sit);
  107.  
  108.       // delete possible intersection between sit_pred and sitsucc
  109.  
  110.       if ((pqit = Y_structure.inf(sit_pred)) != nil) 
  111.       { X_structure.del_item(pqit);
  112.         Y_structure.change_inf(sit_pred,nil);
  113.        }
  114.  
  115.       seg_pred = Y_structure.key(sit_pred);
  116.  
  117.       if (seg_pred.slope() > seg.slope() && seg.intersection(seg_pred,q))
  118.          Y_structure.change_inf(sit_pred,X_structure.insert(sit_pred,q));
  119.  
  120.  
  121.       seg_succ = Y_structure.key(sit_succ);
  122.  
  123.       if (seg.slope() > seg_succ.slope() && seg.intersection(seg_succ,q))
  124.          Y_structure.change_inf(sit,X_structure.insert(sit,q));
  125.  
  126.  
  127.     }
  128.    else  // right end point or intersection 
  129.    { 
  130.      seg = Y_structure.key(sit);
  131.  
  132.      if (p == seg.end())  // right end point  (leave event)
  133.      { 
  134.        x_sweep = p.xcoord();
  135.        y_sweep = p.ycoord();
  136.  
  137.        sit_pred = Y_structure.pred(sit);
  138.        sit_succ = Y_structure.succ(sit);
  139.  
  140.        Y_structure.del_item(sit);
  141.  
  142.        seg_pred = Y_structure.key(sit_pred);
  143.        seg_succ = Y_structure.key(sit_succ);
  144.  
  145.        if (seg_pred.slope() > seg_succ.slope()
  146.             && seg_pred.intersection(seg_succ,q))
  147.           Y_structure.change_inf(sit_pred,X_structure.insert(sit_pred,q));
  148.  
  149.       }
  150.      else   // intersection event
  151.      { 
  152.        result.append(p);
  153.  
  154.        Y_structure.change_inf(sit,nil);
  155.  
  156.        /* Let L be the list of all segments intersecting in p 
  157.           we compute sit0 = L.head(), sit_pred = predecessor of sit0,
  158.           sit1 = L.tail(), and sit_succ = successor of sit1
  159.           by scanning the Y_structure in both directions 
  160.           starting at sit;
  161.  
  162.                                  | --->
  163.                                  |
  164.           sit_succ---------------|---------------- sit_succ
  165.                                  |
  166.           sit1   ______________  |  ______________ sit0
  167.                  ______________\ | /______________
  168.                                 \|/
  169.           sit    ================+================ sit
  170.                  _______________/|\_______________
  171.           sit0   ______________/ | \______________ sit1
  172.                                  |
  173.           sit_pred---------------|---------------- seg_pred
  174.                                  |
  175.                                  |
  176.        */
  177.  
  178.        // search for sit1 & sit_succ upwards starting at sit:
  179.  
  180.        seq_item sit1 = Y_structure.succ(sit);
  181.  
  182.        while ((pqit=Y_structure.inf(sit1)))
  183.        { if (p != X_structure.inf(pqit)) break;
  184.          X_structure.del_item(pqit);
  185.          Y_structure.change_inf(sit1,nil);
  186.          sit1 = Y_structure.succ(sit1);
  187.         }
  188.  
  189.        if (pqit) 
  190.        { X_structure.del_item(pqit);
  191.          Y_structure.change_inf(sit1,nil);
  192.         }
  193.  
  194.        sit_succ = Y_structure.succ(sit1);
  195.  
  196.  
  197.  
  198.        // search for sit_pred downwards starting at sit:
  199.  
  200.        seq_item sit_pred = Y_structure.pred(sit);
  201.  
  202.        while ((pqit=Y_structure.inf(sit_pred)))
  203.        { if (p != X_structure.inf(pqit)) break;
  204.          X_structure.del_item(pqit);
  205.          Y_structure.change_inf(sit_pred,nil);
  206.          sit_pred = Y_structure.pred(sit_pred);
  207.         }
  208.  
  209.        if (pqit) 
  210.        { X_structure.del_item(pqit);
  211.          Y_structure.change_inf(sit_pred,nil);
  212.         }
  213.  
  214.        seq_item sit0 = Y_structure.succ(sit_pred);
  215.  
  216.  
  217.        segment seg0 = Y_structure.key(sit0);
  218.        segment seg1 = Y_structure.key(sit1);
  219.  
  220.        segment seg_succ = Y_structure.key(sit_succ);
  221.        segment seg_pred = Y_structure.key(sit_pred);
  222.  
  223.        // check for intersection between seg_pred and seg1
  224.  
  225.        if (seg_pred.slope() > seg1.slope() && seg_pred.intersection(seg1,q))
  226.           Y_structure.change_inf(sit_pred, X_structure.insert(sit_pred,q));
  227.  
  228.        // check for intersection between seg0 and seg_succ
  229.  
  230.        if (seg0.slope() > seg_succ.slope() && seg_succ.intersection(seg0,q))
  231.           Y_structure.change_inf(sit0,X_structure.insert(sit0,q));
  232.  
  233.  
  234.        // move sweep line into intersection point and reverse the subsequence 
  235.        // of items sit0, ... ,sit1 in the Y-structure
  236.  
  237.        x_sweep = p.xcoord();
  238.        y_sweep = p.ycoord();
  239.  
  240.        Y_structure.reverse_items(sit0,sit1);
  241.  
  242.      } // intersection
  243.    }
  244.   } // Main Loop
  245. } 
  246.  
  247.  
  248. #if !defined(__TEMPLATE_ARGS_AS_BASE__)
  249. declare3(_priority_queue,seq_item,point,bin_heap)
  250. declare3(_priority_queue,seq_item,point,p_heap)
  251. declare3(_sortseq,segment,pq_item,skiplist)
  252. declare3(_sortseq,segment,pq_item,bin_tree)
  253. declare3(_sortseq,segment,pq_item,rs_tree)
  254. declare3(_sortseq,segment,pq_item,rb_tree)
  255. declare3(_sortseq,segment,pq_item,avl_tree)
  256. #endif
  257.  
  258.  
  259.  
  260. main()
  261. { 
  262.   list<segment> seglist;
  263.   list<point>   result;
  264.  
  265.   float T;
  266.  
  267.   int N = read_int("N = ");
  268.  
  269.   init_random(N);
  270.  
  271.   for(int i=0; i < N; i++)
  272.   { double x1 = random(-1000,-100);
  273.     double y1 = random(-1000,1000);
  274.     double x2 = random(100,1000);
  275.     double y2 = random(-1000,1000);
  276.     seglist.append(segment(x1,y1,x2,y2));
  277.    }
  278.  
  279.  
  280.   // we test the algorithm with different priority queue and sorted
  281.   // sequence implementations
  282.  
  283.   priority_queue<seq_item,point>          f_heap_queue;    // Fibonacci heap
  284.  
  285. #if defined(__TEMPLATE_ARGS_AS_BASE__)
  286.  _priority_queue<seq_item,point,bin_heap> bin_heap_queue;  // binary heap
  287.  _priority_queue<seq_item,point,p_heap>   pair_heap_queue; // pairing heap
  288.  _sortseq<segment,pq_item,skiplist>       skiplist_seq;    // skip list
  289.  _sortseq<segment,pq_item,bin_tree>       bin_tree_seq;
  290.  _sortseq<segment,pq_item,rs_tree>        rs_tree_seq;
  291.  _sortseq<segment,pq_item,rb_tree>        rb_tree_seq;
  292.  _sortseq<segment,pq_item,avl_tree>       avl_tree_seq;
  293. #else
  294.  _priority_queue(seq_item,point,bin_heap) bin_heap_queue;
  295.  _priority_queue(seq_item,point,p_heap)   pair_heap_queue;
  296.  _sortseq(segment,pq_item,skiplist)       skiplist_seq;
  297.  _sortseq(segment,pq_item,bin_tree)       bin_tree_seq;
  298.  _sortseq(segment,pq_item,rs_tree)        rs_tree_seq;
  299.  _sortseq(segment,pq_item,rb_tree)        rb_tree_seq;
  300.  _sortseq(segment,pq_item,avl_tree)       avl_tree_seq;
  301. #endif
  302.  
  303.  
  304.  
  305.   cout << "sweep segments (f_heap   / skiplist)   :   ";
  306.   cout.flush(); 
  307.   T = used_time();
  308.   SWEEP(f_heap_queue,skiplist_seq,seglist,result);
  309.   cout<< string(" # = %d time = %6.2f sec",result.length(), used_time(T));
  310.   newline;
  311.  
  312.   cout << "sweep segments (bin_heap / skiplist)   :   ";
  313.   cout.flush(); 
  314.   T = used_time();
  315.   SWEEP(bin_heap_queue,skiplist_seq,seglist,result);
  316.   cout<< string(" # = %d time = %6.2f sec",result.length(), used_time(T));
  317.   newline;
  318.  
  319.   cout << "sweep segments (pairheap / skiplist)   :   ";
  320.   cout.flush(); 
  321.   T = used_time();
  322.   SWEEP(pair_heap_queue,skiplist_seq,seglist,result);
  323.   cout<< string(" # = %d time = %6.2f sec",result.length(), used_time(T));
  324.   newline;
  325.   newline;
  326.  
  327.  
  328.   cout << "sweep segments (f_heap   / bin_tree)   :   ";
  329.   cout.flush(); 
  330.   T = used_time();
  331.   SWEEP(f_heap_queue,bin_tree_seq,seglist,result);
  332.   cout<< string(" # = %d time = %6.2f sec",result.length(), used_time(T));
  333.   newline;
  334.  
  335.  
  336.   cout << "sweep segments (bin_heap / bin_tree)   :   ";
  337.   cout.flush(); 
  338.   T = used_time();
  339.   SWEEP(bin_heap_queue,bin_tree_seq,seglist,result);
  340.   cout<< string(" # = %d time = %6.2f sec",result.length(), used_time(T));
  341.   newline;
  342.  
  343.  
  344.   cout << "sweep segments (pairheap / bin_tree)   :   ";
  345.   cout.flush(); 
  346.   T = used_time();
  347.   SWEEP(pair_heap_queue,bin_tree_seq,seglist,result);
  348.   cout<< string(" # = %d time = %6.2f sec",result.length(), used_time(T));
  349.   newline;
  350.   newline;
  351.  
  352.  
  353.  
  354.   cout << "sweep segments (f_heap   / rs_tree)    :   ";
  355.   cout.flush(); 
  356.   T = used_time();
  357.   SWEEP(f_heap_queue,rs_tree_seq,seglist,result);
  358.   cout<< string(" # = %d time = %6.2f sec",result.length(), used_time(T));
  359.   newline;
  360.  
  361.   cout << "sweep segments (bin_heap / rs_tree)    :   ";
  362.   cout.flush(); 
  363.   T = used_time();
  364.   SWEEP(bin_heap_queue,rs_tree_seq,seglist,result);
  365.   cout<< string(" # = %d time = %6.2f sec",result.length(), used_time(T));
  366.   newline;
  367.  
  368.   cout << "sweep segments (pairheap / rs_tree)    :   ";
  369.   cout.flush(); 
  370.   T = used_time();
  371.   SWEEP(pair_heap_queue,rs_tree_seq,seglist,result);
  372.   cout<< string(" # = %d time = %6.2f sec",result.length(), used_time(T));
  373.   newline;
  374.   newline;
  375.  
  376.  
  377.  
  378.   cout << "sweep segments (f_heap   / rb_tree)    :   ";
  379.   cout.flush(); 
  380.   T = used_time();
  381.   SWEEP(f_heap_queue,rb_tree_seq,seglist,result);
  382.   cout<< string(" # = %d time = %6.2f sec",result.length(), used_time(T));
  383.   newline;
  384.  
  385.   cout << "sweep segments (bin_heap / rb_tree)    :   ";
  386.   cout.flush(); 
  387.   T = used_time();
  388.   SWEEP(bin_heap_queue,rb_tree_seq,seglist,result);
  389.   cout<< string(" # = %d time = %6.2f sec",result.length(), used_time(T));
  390.   newline;
  391.  
  392.   cout << "sweep segments (pairheap / rb_tree)    :   ";
  393.   cout.flush(); 
  394.   T = used_time();
  395.   SWEEP(pair_heap_queue,rb_tree_seq,seglist,result);
  396.   cout<< string(" # = %d time = %6.2f sec",result.length(), used_time(T));
  397.   newline;
  398.   newline;
  399.  
  400.  
  401.  
  402.  
  403.   cout << "sweep segments (f_heap   / avl_tree)   :   ";
  404.   cout.flush(); 
  405.   T = used_time();
  406.   SWEEP(f_heap_queue,avl_tree_seq,seglist,result);
  407.   cout<< string(" # = %d time = %6.2f sec",result.length(), used_time(T));
  408.   newline;
  409.  
  410.   cout << "sweep segments (bin_heap / avl_tree)   :   ";
  411.   cout.flush(); 
  412.   T = used_time();
  413.   SWEEP(bin_heap_queue,avl_tree_seq,seglist,result);
  414.   cout<< string(" # = %d time = %6.2f sec",result.length(), used_time(T));
  415.   newline;
  416.  
  417.   cout << "sweep segments (pairheap / avl_tree)   :   ";
  418.   cout.flush(); 
  419.   T = used_time();
  420.   SWEEP(pair_heap_queue,avl_tree_seq,seglist,result);
  421.   cout<< string(" # = %d time = %6.2f sec",result.length(), used_time(T));
  422.   newline;
  423.   newline;
  424.  
  425.  
  426.   return 0;
  427. }
  428.